package com.leetcode;

/**
 * 744. 寻找比目标字母大的最小字母
 * 二分搜索法O(logn) 比较复杂的写法
 *
 * @author fy
 * @date 2022/4/27 15:11
 */
public class Solution744_1 {

    public char nextGreatestLetter(char[] letters, char target) {
        if (letters == null || letters.length < 2) {
            throw new RuntimeException("letters is wrong");
        }
        int n = letters.length;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            // 为了处理可能重复的相同字符, 这段代码可以去掉
            if (letters[mid] == target) {
                if (mid + 1 <= n - 1) {
                    if (letters[mid] != letters[mid + 1]) {
                        return letters[mid + 1];
                    } else {
                        l = mid + 1;
                    }
                } else {
                    return letters[0];
                }
            } else if (letters[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        // 处理超出数组最后范围时取第一个
        if (l <= n - 1) {
            return letters[l];
        } else {
            return letters[0];
        }
    }

}
